# 删除链表的倒数第n个结点: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 这题难点就在于设立首元结点，统一删除操作其他比较平常
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        """
            和876号算法题一样，使用双指针解决问题：快慢指针，是两个指针相隔 n 的距离。 快指针到达末尾时，慢指针刚好是到达倒数n的位置
        """
        # 1. 注意： 删除的可能是第一个节点，需要设立首元结点，统一删除逻辑
        dumpy = ListNode(0, head)
        low = fast = dumpy
        # 1. 快指针和慢指针相隔 n 长度
        for i in range(n-1): fast = fast.next
        # 2. 要做删除操作，所以要停在删除节点的前一个节点
        while fast.next.next:
            fast = fast.next
            low = low.next
        # 3. 删除
        low.next = low.next.next
        
        head = dumpy.next
        return head

